package site.wanjiahao.union;

import java.util.Arrays;

/**
 * Quick Union
 * find O(logn)
 * Union O(logn)
 * <p>
 * 在union过程中，可能会退化为链表。所以需要控制合并的过程
 */
public class UnionFind_QU_S extends UnionFind_QU {

    int[] size;

    public UnionFind_QU_S(int capacity) {
        super(capacity);
        size = new int[capacity];
        // 每个节点的size都为1
        Arrays.fill(size, 1);
    }

    @Override
    public void union(int v1, int v2) {
        // 将v1元素的父元素置为
        int p1 = find(v1);
        int p2 = find(v2);
        // 两父元素相等，不用进行任何操作
        if (p1 == p2) return;
        // 将元素数量少的一方，嫁接到元素数量多的一方上
        if (size[p1] > size[p2]) {
            parents[p2] = p1;
            size[p1] += size[p2];
        } else {
            parents[p1] = p2;
            size[p2] += size[p1];
        }
    }
}
